#include <iostream>
#include "LinkedList.h"
using namespace std;

// 100.00 %
class Solution
{
public:
  ListNode *partition(ListNode *head, int x)
  {
    if (head == NULL)
      return NULL;
    ListNode *preNode = head, *curNode = head->next;
    ListNode *signNode = head->val < x ? head : NULL;
    while (curNode != NULL)
    {
      if (curNode->val < x)
      {
        if (signNode == NULL)
        {
          preNode->next = curNode->next;
          curNode->next = head;
          signNode = curNode;
          head = curNode;
          curNode = preNode->next;
        }
        else
        {
          if (signNode == preNode)
          {
            preNode = preNode->next;
            curNode = curNode->next;
            signNode = signNode->next;
          }
          else
          {
            preNode->next = curNode->next;
            curNode->next = signNode->next;
            signNode->next = curNode;
            signNode = curNode;
            curNode = preNode->next;
          }
        }
      }
      else
      {
        preNode = preNode->next;
        curNode = curNode->next;
      }
    }
    return head;
  }
};

int main(int argc, char const *argv[])
{
  int arr[] = {3, 1, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  ListNode *list = createLinkedList(arr, n);
  int x = 3;
  printLinkedList(list);

  list = Solution().partition(list, x);

  printLinkedList(list);
  deleteLinkedList(list);
  return 0;
}
